#include "Bitmap.h"
#include <math.h>

//hash函数
unsigned int BKDRhash(const char *str){
    unsigned int seed=31;
    unsigned int hash=0;
    while(*str){
        hash=hash*seed+(*str++);
    }
    return (hash & 0x7FFFFFFF);
}

//计算哈希空间
unsigned int Hspace(FILE *f){
    double e;
    unsigned int n=0;
    char row[1024];
    while (fgets(row, 1024, f)!=NULL)
        n++;

    printf("可接受误差：");
    scanf("%lf",&e);
    n=n/log(n*e*e+1);

    return n;
}

//位图计数算法
unsigned int BM_COUNT(BitMap *bm,FILE *f,unsigned int hspace){
    //unsigned int bitnum=MAX_BIT/v;
    char row[1024];
    char *flowid;
    unsigned int t=0;
    unsigned int hash=1;
    while (fgets(row, 1024, f)!=NULL) {//按行读取数据
        flowid=strtok(row, ","); 
        hash=BKDRhash(flowid);
        hash%=hspace;//对整个哈希空间做求余运算
        if(hash!=t&&hash<(bm->size)){
            BMSet1(bm,hash);
            t=hash;
        }
        else{
            continue;
        }
    }
    unsigned int count=Count(bm);

    return count;
}

//估值计算
unsigned int Result(unsigned int count,unsigned int bitnum){
    double i,j;
    unsigned int result;
    i=(bitnum*1.0)/(bitnum-count);
    j=log(i);
    result=bitnum*j;

    return result;
}

int main(){
    unsigned int bitnum=1;
    BitMap *t;
    BMInit(t);//初始化
    FILE *f;
    fpos_t header;
    char file[100];
    double v;//采样因子
    unsigned int count;
    unsigned int result;
    unsigned int hspace;

    int s=1;
    while(s){
        printf("---------------------------------------------------------------------------\n");
        printf("选择算法：1.直接位图算法  2.虚拟位图算法  0.退出程序\n");
        scanf("%d",&s);
        switch(s){
            case 1://直接位图算法
                printf("输入文件路径：");
                scanf("%s",file);
                f=fopen(file,"r");
                if(f!=NULL){
                    fgetpos(f, &header);//记录文件启示位置
                    hspace=Hspace(f);
                    bitnum=hspace;
                    BMCreat(t,bitnum);///确保每次循环位图为全0
                    fsetpos(f, &header);
                    count=BM_COUNT(t,f,hspace);
                    result=Result(count,t->size);
                    printf("流数量估计值为%u\n",result);
                    fclose(f);
                }
                else
                    printf("文件打开失败，请检查文件路径\n");
            break;

            case 2://虚拟位图算法
                printf("输入文件路径：");
                scanf("%s",file);
                f=fopen(file,"r");
                if(f!=NULL){
                    fgetpos(f, &header);//记录文件启示位置
                    hspace=Hspace(f);
                    printf("输入采样因子v：");
                    scanf("%lf",&v);
                    bitnum=hspace*v;//确定虚拟位图大小
                    BMCreat(t,bitnum);///确保每次循环位图为全0
                    fsetpos(f, &header);
                    count=BM_COUNT(t,f,hspace);
                    result=Result(count,t->size)/v;
                    printf("流数量估计值为%u\n",result);
                    fclose(f);
                }
                else
                    printf("文件打开失败，请检查文件路径\n");
            break;

            case 0:
                printf("程序已结束！\n");
                printf("---------------------------------------------------------------------------\n");
            break;

            default:
            break;
        }
        //BMZero(t);
    }
    BMDestroy(t);
    return 0;
}